package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname NSumModel
 * @description 计算n数和的通用模板
 * @date 2023/05/29 22:52
 * <p>
 * ******************************************************
 */
public class NSumModel {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        // n 为 4，从 nums[0] 开始计算和为 target 的四元组
        return nSumTarget(nums, 4, 0, target);
    }

    /* 注意：调用这个函数之前一定要先给 nums 排序 */
    public List<List<Integer>> nSumTarget(int[] nums, int n, int start, long target) {


        int sz = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        // 至少是 2Sum，且数组大小不应该小于 n
        if (n < 2 || sz < n) return res;
        // 2Sum 是 base case
        if (n == 2) {
            // 左右指针
            int lo = start, hi = nums.length - 1;
            while (lo < hi) {
                // 记录索引 lo 和 hi 最初对应的值
                int left = nums[lo], right = nums[hi];
                long sum = nums[lo] + nums[hi];
                if (sum > target) {
                    while (lo < hi && nums[hi] == right) hi--;
                } else if (sum < target) {
                    while (lo < hi && nums[lo] == left) lo++;
                } else {
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[lo]);
                    list.add(nums[hi]);
                    res.add(list);
                    // 跳过所有重复的元素
                    while (lo < hi && nums[lo] == left) lo++;
                    while (lo < hi && nums[hi] == right) hi--;
                }
            }
        } else {

            for (int i = start; i < nums.length; i++) {
                final List<List<Integer>> sub = nSumTarget(nums,n-1, i + 1, target - nums[i]);
                for (List<Integer> list : sub) {
                    list.add(nums[i]);
                    res.add(list);
                }
                // 跳过第一个数字重复的情况，否则会出现重复结果
                while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
            }
        }
        return res;
    }
}
